/*
import java.util.Stack;

public class Solution {
    public String ReverseSentence(String str) {
        // 栈
        String ret = "";
        String[] arr = str.split(" ");

        Stack<String> stack = new Stack<>();

        for (String s: arr) {
            stack.push(s);
        }

        while (!stack.isEmpty()) {
            ret += stack.pop();
            if (stack.size() != 0)
                ret += " ";
        }

        return ret;         
    }
}
*/

import java.util.*;
public class Solution {
    //字符串反转函数
    private void reverse(char [] c, int l, int h){
        //双指针反转
        while(l < h)
            swap(c, l++, h--);
    }
    //字符交换函数
    private void swap(char [] c, int l, int h){
        char temp = c[l];
        c[l] = c[h];
        c[h] = temp;
    }
    
    public String ReverseSentence(String str) {
        int n = str.length();
        char[] c = str.toCharArray();
        //第一次整体反转
        reverse(c, 0, n - 1);
        for(int i = 0; i < n; i++){
            int j = i;
            //以空格为界找到一个单词
            while(j < n && c[j] != ' ') 
                j++;
            //将这个单词反转
            reverse(c, i, j - 1); 
            i = j;
        }
        return new String(c);
    }
}
